package com.hdu.other.dp.maxIncLen;

public class lc2111 {
    class Solution {
        public int kIncreasing(int[] arr, int k) {
            int n = arr.length;
            int ans = 0;
            // 4, 1, 5, 2, 6, 2
            // k = 2
            // 0 2 4 6
            // 1 3 5 7

            // k = 3
            // 0 3 6 9
            // 1 4 7 10
            // 2 5 8 11
            int[] tmp = new int[n];
            int[] ends = new int[n];
            for (int i = 0; i < k; i++) {
                int index = 0;
                for (int j = i; j < n; j += k)
                {
                    tmp[index++] = arr[j];
                }
                int len = 0;
                for (int j = 0; j < index; j++) {
                    int pos = bs(ends, len, tmp[j]);
                    if (pos == -1) {
                        ends[len++] = tmp[j];
                    } else {
                        ends[pos] = tmp[j];
                    }
                }
                ans += index - len;
            }
            return ans;
        }

        int bs(int[] ends, int len, int target) {
            int l = 0, r = len - 1, ans = -1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (ends[mid] > target) {
                    ans = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            return ans;
        }
    }
}
